﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include <list>
#include <unordered_map>

class LRUCache 
{
public:
    LRUCache(int capacity)
        :_capacity(capacity)
    {}

    int get(int key)
    {
        auto ret = _hashMap.find(key);
        if (ret != _hashMap.end())
        {
            // 更新key对应值的位置
            LTIter it = ret->second;
            // 1.erase + push_front 更新迭代器，原迭代器失效
            // 2.splice 转移节点
            _LRUList.splice(_LRUList.begin(), _LRUList, it);

            return it->second;
        }

        else
        {
            return -1;
        }
    }

    void put(int key, int value)
    {
        // 1.新增
        // 2.更新
        auto ret = _hashMap.find(key);
        if (ret == _hashMap.end())
        {
            // 满了，先删除LRU的数据
            if (_capacity == _hashMap.size())
            {
                pair<int, int> back = _LRUList.back();
                _hashMap.erase(back.first);
                _LRUList.pop_back();
            }

            _LRUList.push_front(make_pair(key, value));
            _hashMap[key] = _LRUList.begin();
        }
        else
        {
            // 更新key对应值的位置
            LTIter it = ret->second;
            it->second = value;

            // 1.erase + push_front 更新迭代器，原迭代器失效
            // 2.splice 转移节点
            _LRUList.splice(_LRUList.begin(), _LRUList, it);
        }
    }

private:
    typedef list<pair<int, int>>::iterator LTIter;

    // hash 做到查找更新是 O(1)
    unordered_map<int, LTIter> _hashMap;

    // LRU 假设尾部数据就是最近最少用
    list<pair<int, int>> _LRUList;
    size_t _capacity;
};

int main() 
{
    int capacity = 2;

    LRUCache* obj = new LRUCache(capacity);

    // -1
    cout << obj->get(1) << endl;

    // [2, 2]
    obj->put(2, 2);

    // [2, 2]、[3, 3];
    obj->put(3, 3);

    // 3
    cout << obj->get(3) << endl;


	return 0;
}